You
are given a set S of integers between -30000 and 30000 (inclusive).
Find
the total number of sextuples (a, b, c, d, e,
f) : a, b, c, d,
e, f Î S, d ≠ 0, that satisfy:
(a * b
+ c) / d – e = f
Input. The first line contains integer n (1 ≤ n ≤
100), the size of a set S. Elements of S are given in the next n lines, one integer per line. Given
numbers will be distinct.
Output. Output the total number of plausible sextuples.
|
Sample Input |
Sample Output |
|
2 2 3 |
4 |
сортировка
Перепишем равенство в виде a * b
+ c = (f + e) * d. Занесем в массив m1 все возможные
значения выражения a * b + c
(a, b, c Î
S). Занесем в массив m2 все возможные значения выражения (f + e) * d (f,
e, d Î S). Отсортируем массивы m1 и m2.
Найдем общие числа в двух массивах. Пусть число x содержится в m1 p раз,
а в m2 q раз. Тогда количество
искомых шестерок следует увеличить на p
* q.
Реализация
алгоритма
#include <cstdio>
#include <algorithm>
#define N 200
using namespace std;
int i, j,
k, n;
int
s[101];
int a, b,
c, d, e, f, g, res;
int pi,
pj, qi, qj;
int
m1[N*N*N+10], m2[N*N*N+10];
int main(void)
{
scanf("%d",&n);
for(i = 0; i
< n; i++) scanf("%d",&s[i]);
for(i = a =
0; a < n; a++)
for(b = 0; b
< n; b++)
for(c = 0; c
< n; c++)
m1[i++] = s[a]*s[b]+s[c];
sort(m1,m1+i);
for(j = d =
0; d < n; d++)
if (s[d] !=
0)
for(e = 0;
e < n; e++)
for(f = 0;
f < n; f++)
m2[j++] = s[d] * (s[e] + s[f]);
sort(m2,m2+j);
for(res = pi
= pj = 0;;)
{
if (m1[pi]
< m2[pj]) pi++; else
if (m1[pi]
> m2[pj]) pj++; else
{
qi = pi; qj = pj;
while((m1[qi]
== m1[pi]) && (qi < i)) qi++;
while((m2[qj]
== m2[pj]) && (qj < j)) qj++;
res += (qi - pi) * (qj - pj);
if ((qi
== i) || (qj == j)) break;
pi
= qi; pj = qj;
}
}
printf("%d\n",res);
return 0;
}